/**
 * @a https://leetcode.cn/problems/top-k-frequent-words/
 */

#include "../common.h"

// heap
class Solution {
    using str_int_t=pair<string,int>;
private:
    struct cmp{
        bool operator()(str_int_t p1, str_int_t p2){
            if(p1.second == p2.second){
                return p1.first < p2.first;
            }
            return p1.second > p2.second;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string,int> mp;
        for(auto &word: words){
            ++mp[word];
        }
        priority_queue<str_int_t, vector<str_int_t>,cmp> pq;
        for(auto &item:mp)
        {
            pq.push(item);
            if(pq.size() > k) pq.pop();
        }
        vector<string> ret;
        while(pq.size()){
            ret.push_back(pq.top().first);
            pq.pop();
        }
        reverse(ret.begin(),ret.end());
        return ret;
    }
};